10944. Орехи для орехов
На острове разбросаны
орехи. Лари хочет собрать все орехи по кратчайшему пути и вернуться на исходное
место.
Вход.
Первая строка каждого теста содержит длину x и ширину y острова (x,
y < 20). Далее следуют x строк, описывающих карту острова.
Карта состоит из символов ‘L’ (начальное местоположение Лари), ‘.’ (пустое
место), ‘#’ (орех). Лари может
передвигаться за один шаг в любом из 8 соседних направлений (по горизонтали,
вертикали и диагонали). Количество орехов не более 15. Символ ‘L’ на карте
только один.
Выход. Для каждого теста вывести
минимальное число шагов, которое следует пройти Лари, чтобы собрать все орехи и
вернуться на исходное место.
Пример входа
5 5
L....
#....
#....
.....
#....
5 5
L....
#....
#....
.....
#....
Пример выхода
8
8
РЕШЕНИЕ
задача коммивояжера, NP полнота,
динамическое программирование
Анализ алгоритма
Классическая задача коммивояжера.
Следует найти цикл минимальной длины, проходящий по всем вершинам графа. Или то
же самое что найти гамильтонов цикл минимальной длины. Задача является NP
полной и требует экспоненциального времени для ее решения относительно числа
вершин в графе.
Пусть
n – число вершин в графе. Каждому ореху и начальному местоположению Лари
поставим в соответствие вершину графа. Из условия задачи следует, что n £ 16. Все
вершины графа будут попарно соединены (решается евклидова задача коммивояжера).
Длина ребра, соединяющего вершины которым соответствуют координаты (a, b)
и (c, d), равна max( |a – c|, |b – d|
). Матрицу смежности построенного графа храним в двумерном массиве m.
Можно сгенерировать при помощи
функции next_permutation все возможные перестановки чисел от 1 до n,
каждой перестановке будет соответствовать гамильтонов цикл. Ищем минимальное
значение среди всех длин таких циклов. Приведенный алгоритм требует n!
времени, что для n = 16 слишком много (следует перебрать 16! =
20922789888000 вариантов).
Используя метод динамического
программирования, можно решить задачу с оценкой O(2n) по
используемой памяти и O(n2 * 2n) по времени
работы алгоритма. При n = 16 следует перебрать 16777216 вариантов, что
реально по времени.
Для
непустого подмножества S Í {1, 2, …, n} и каждой
вершины i Î S определим
dp(S, i) как длину кратчайшего пути, начинающегося в первой (начальной)
вершине, проходящего по всем вершинам из множества S \ {i} в
произвольном порядке и оканчивающегося в вершине i. Тогда имеют место
равенства:
dp({1, i}, i) = m[1][i],
dp(S, i) = 
(dp(S \ {i}, j) + m[j, i] )
Значения dp(S, i)
пересчитываем динамически, запоминая их в массиве dp. Гамильтонов цикл
минимальной длины равен
(dp({1, 2, ..., n}, j) + m[j, 1] )
Пример
В первом тесте достаточно пройти
вниз острова (4 шага), собрав по пути все орехи, и подняться вверх к исходному
месту (еще 4 шага).
Реализация алгоритма
Определим переменную INF, условно
равную бесконечности, максимально возможное число вершин в графе MAX и массив
dp, в котором будем хранить динамически пересчитываемые значения dp(S, i).
Каждое подмножество S будем хранить в виде числа, в котором i - ый бит
равен 1, если вершина с номером i в нем присутствует, и нулю иначе.
Например, при n = 5 подмножество {1, 4, 5} кодируется числом 110012
= 25.
#define INF 100000000
#define MAX 16
int dp[1<<MAX][MAX+1];
Карту острова храним в символьном
массиве mas, координаты орехов и начального положения Лари – в массивах x
и y, матрицу смежности графа – в массиве m.
int x[21], y[21], m[21][21];
char mas[21][21];
Функция solve вычисляет значение
dp(S, last), где множество S кодируется целым числом mask. При
этом S \ {last} равно mask ^ 1<<(last – 1). Далее
перебираем все i, i Î S \ {last} и ищем
минимальное значение res среди dp(S \ {last}, i) + m[i,
last]. Переменная res указывает на ячейку dp[mask][last], так что с изменением res
изменяется и само значение dp[mask][last].
int solve(int
mask,int last)
{
int i, cr;
int &res
= dp[mask][last];
if(res <
0)
{
mask ^= 1 << (last - 1);
res = INF;
for(i = 1;
i <= nuts; ++i)
if(mask
& (1 << (i - 1)))
{
cr = solve(mask,i) + m[i][last];
if(cr<res)
res = cr;
}
}
return res;
}
Основной цикл программы. Читаем
данные острова в массив mas, заносим координаты орехов в массивы x и y.
Начальное местоположение Лари сохраняем в (x[1], y[1]).
while(scanf("%d
%d\n",&xx,&yy) == 2)
{
for(i = 0; i
< xx; i++) gets(mas[i]);
nuts = 1;
for(i = 0; i
< xx; i++)
for(j = 0; j
< yy; j++)
if
(mas[i][j] == 'L')
{
x[1] = i; y[1] = j;
} else
if
(mas[i][j] == '#')
{
x[++nuts] = i; y[nuts] = j;
}
Число вершин графа, равное
количеству орехов на острове плюс один (начальное состояние Лари), хранится в
переменной nuts. Если орехов на острове нет, то выводим 0.
if (nuts ==
1)
{
printf("0\n");
continue;
}
Строим матрицу смежности графа m.
Вычисляем длины ребер.
memset(m,0x3F,sizeof(m));
for(i = 1; i
< nuts; i++)
for(j = i +
1; j <= nuts; j++)
m[i][j] = m[j][i] = max(abs(x[i] - x[j]), abs(y[i] - y[j]));
Изначально значения dp(S, i)
неизвестны, положим их равными некоторому отрицательному числу. При этом
dp({1}, 1) = 0 (минимальный путь из первой вершины в нее же без посещения
других вершин равен нулю). В переменной total храним искомую минимальную
длину цикла.
memset(dp,-1,sizeof(dp));
dp[1][1] = 0; total = INF;
n2 = 1 << nuts;
Вычисляем гамильтонов цикл
минимальной длины и печатаем результат. Значение n2 – 1 соответствует
множеству {1, 2, 3, ..., nuts}. Вычисляем минимум среди всех значений
dp({1, 2, ..., nuts}, i) + m[i, 1], 2 £ i
£ nuts.
for(i = 2; i
<= nuts; i++)
{
temp = solve(n2-1,i) + m[i][1];
if(temp
< total) total = temp;
}
printf("%d\n",total);
}